Hashing is a well-known method in the computer industry, by which large number values (called Keys and denoted by “K”) are compressed (Hashed) to smaller number values (called hashed numbers and denoted by “h”), in order to make it practical to use it as index for lookup tables. Using the key “K” directly as a lookup table index, without Hashing, requires a very large memory of size 2^n (2 to the power n, where n is the size of K in number of bits), which may have very little data scattered in it. Hashing will basically optimize the memory size requirements when large number values are to be used for indexing.
A well-known problem in Hashing is called “Collision”. Collision happens when two or more Keys (K) are hashed to the same small Hashed value (h). Collision is possible because the mapping from the Keys to Hashed values is not a 1:1 relationship, rather, it is an N:1 relationship, in which many (N) Keys can map the same Hashed value (h).
There are also numerous Hashing functions that are used to convert Keys (K) to Hashed values (h). The ideal Hashing functions are those that are more random and have less correlation between Keys (K) and Hashed values (h). There are also numerous methods in the industry to resolve hashing collisions, which include, but are not limited to:                Chaining        Overflow areas        Re-hashing        Using neighboring slots (linear probing)        Quadratic probing        Random probing.        
This invention uses unique Hashing functions and Hashing collision mechanisms that are novel. The main purpose of this invention is, for example, for Ethernet MAC address lookup and double VLAN tag lookups, but it can be used for other lookup purposes, as well.